\documentclass[10pt]{article}
\usepackage{amsmath}
\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}

\newcommand{\problem}[2][No]{\noindent{\sc Problem #1.} #2}
\newcommand{\solution}{\noindent{\sc Solution.}}
\newcommand{\answer}[1]{\noindent{\sc Answer. }#1}
\newcommand{\complexity}{\noindent{\sc Complexity }}
\newcommand{\reference}{\noindent{\sc Reference }}
\newcommand{\seealso}{\noindent{\sc See Also }}

\newcommand{\given}{\,|\,}
\newcommand{\divides}{\,|\,}
\newcommand{\BigO}{\mathcal{O}}

\newcommand{\vl}{\mathbf{l}}

\begin{document}

\problem[186]{Connectedness of a network.}

Here are the records from a busy telephone system with 1,000,000 users:
\begin{center}
\begin{tabular}{c c c}
\hline
RecNr & Caller & Called \\
\hline
1 & 200007 & 100053 \\
2 & 600183 & 500439 \\
3 & 600863 & 701497 \\
$\cdots$ & $\cdots$ & $\cdots$ \\
\hline
\end{tabular}
\end{center}

The telephone number of the caller and the callee in record $n$ are $\text{Caller}(n) = S_{2n-1}$ and $\text{Callee}(n) = S_{2n}$, where $\{S_k\}$ come from the \emph{Lagged Fibonacci Generator}:

For $1 \le k \le 55$, $S_k = (100003 - 200003k + 300007k^3) \text{ mod } 1000000,$

For $k \ge 56$, $S_k = (S_{k-24} + S_{k-55}) \text{ mod } 1000000$.

If $\text{Caller}(n) = \text{Callee}(n)$ then the user is assumed to have mis-dialed and the call fails; otherwise the call is successful.

We say that a pair of users $X$ and $Y$ are \emph{(directly) connected} if $X$ ever calls $Y$ or $Y$ ever calls $X$. In addition, $X$ and $Z$ are \emph{(indirectly) connected} if they are both connected, either directly or indirectly, to some other user $Y$.

Any user $X$ is said to be connected to himself.

The Prime Minister's phone number is 524287. After how many successful calls, not counting misdials, will at least 99\% of all telephone users, including the PM himself, be connected (directly or indirectly) to the PM?

\solution

This problem can be solved by the standard disjoint-set algorithm. See the Wiki on disjoint-set for details on the algorithm. In the implementation, we compare the disjoint-set linked-list data structure with the disjoint-set forest data structure, and find the latter algorithm performing slightly better. 

Note 1. The Lagged Fibonacci Generator is a pseudo-random number generator. The choice of a particular generator does not have much effect on the solution.

Note 2. The PM's number, 524287, is supposed to be ``funny'' in the sense that it's a prime number and its hexadecimal form is 0x7ffff.

\answer{2325629}

\complexity

Time complexity: $\BigO(n \log n)$

Space complexity: $\BigO(n)$

\reference

http://en.wikipedia.org/wiki/Disjoint-set\_data\_structure

http://en.wikipedia.org/wiki/Lagged\_Fibonacci\_generator

http://www.numberempire.com/524287

\end{document} 